function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

var dfs = function(root) {
    if (root == null) return

    dfs(root.left)
    dfs(root.right)
    console.log(root.val)
}

var bfs = function (root) {
    if (root == null) return []
    // 存放最终的结果
    let result = []
    // 存放子数组
    // 存放过度数组
    let temp = []
    let queue = []
    queue.push(root)
    let flag = false
    while (queue.length != 0) {
        while (queue.length != 0) {
            temp.push(queue.shift())
        }
        let subResult = []
        while (temp.length != 0) {
            let treeNode = temp.shift()
            subResult.push(treeNode.val)
            if (treeNode.left != null) queue.push(treeNode.left)
            if (treeNode.right != null) queue.push(treeNode.right)
        }
        if (flag) {
            subResult.reverse()
        }
        flag = !flag
        result.push(subResult)
    }
    return result
}

let root = new TreeNode(4)
root.left =  new TreeNode(2)
root.right =  new TreeNode(5)
root.left.left =  new TreeNode(1)
root.left.right =  new TreeNode(3)
console.log(bfs(root))


